Diffie-Hellman key agreement provided the first practical solution to the key distribution problem, in cryptographic systems. The key agreement protocol allowed two parties never having met in advance or shared key material to establish a shared secret by exchanging messages over an open (unsecured) channel. The security rests on the intractability of the Diffie-Hellman problem and the related problem of computing discrete logarithms.
With the advent of the Internet and such like the requirement for large-scale distribution of public keys and public key certificates are becoming increasingly important. Public-key certificates are a vehicle by which public keys may be stored, distributed or forwarded over unsecured media without danger of undetectable manipulation. The objective is to make one parties' public key available to others such that its authenticity and validity are verifiable.
A public-key certificate is a data structure consisting of a data part and a signature part. The data part contains cleartext data including as a minimum, public key and a string identifying the party to be associated therewith. The signature part consists of the digital signature of a certification authority (CA) over the data part, thereby binding the entities identity to the specified public key. The CA is a trusted third party whose signature on the certificate vouches for the authenticity of the public key bound to the subject entity.
Identity-based systems (ID-based system) resemble ordinary public-key systems, involving a private transformation and a public transformation, but parties do not have explicit public keys as before. Instead, the public key is effectively replaced by a party's publicly available identity information (e.g. name or network address). Any publicly available information, which uniquely identifies the party and can be undeniably associated with the party, may serve as identity information.
An alternate approach to distributing public keys involves implicitly certified public keys. Here explicit user public keys exist, but they must be reconstructed rather than transported by public-key certificates as in certificate based systems. Thus implicitly certified public keys may be used as an alternative means for distributing public keys (e.g. Diffie-Hellman keys).
An example of an implicitly certified public key mechanism is known as Gunther's implicitly-certified (ID-based) public key method. In this method:                1. A trusted server T selects an appropriate fixed public prime p and generator α of Zp*. T selects a random integer t, with 1≦t≦p−2 and gcd(t, p−1)=1, as its private key, and publishes its public key u=αt mod p, along with α, p.        2. T assigns to each party A a unique name or identifying string IA and a random integer kA with gcd(kA, p−1)=1. T then computes PA=αKA mod p. PA is A's KEY reconstruction public data, allowing other parties to compute (PA)αbelow.        3. Using a suitable hash function h, T solves the following equation for a:H(IA)≡t.PA+kA a(mod p−1)        4. T securely transmits to A the pair (r,s)=(PA, a), which is T's ElGamal signature on IA (a is A's private key for Diffie-Hellman key-agreement)        5. Any other party can then reconstruct A's Diffie-Hellman public key PAα entirely from publicly available information (α, IA, u, PA, p) by computing:PAα≡αh(IA)u−PA mod p         
Thus for discrete logarithm problems, signing a certificate needs one exponentiation operation, but reconstructing the ID-based implicitly-verifiable public key needs two exponentiations. It is known that exponentiation in the group Zp* and its analog scalar multiplication of a point in E(Fq) is computationally intensive. For example an RSA scheme is extremely slow compared to elliptic curve systems. However despite the resounding efficiency of EC systems over MSA type systems this is still a problem particularly for computing devices having limited computing power such as “smart cards”, pagers and such like.